package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         343,
		Discription: "将指定数拆分成若干个正整数（至少两个）之后，这些正整数之积的最大值",
		Level:       2,
		Labels: map[string]int{
			"动态规划": 1,
			"数学": 1,
		},
	})
}

func IntegerBreak(n int) int {
	dp := make([]int, n+1)
	//除了n外，其它位置的初始值都可以是它们自己，因为之后要凑成和为n肯定还有其它数
	for i := 1; i <= n-1; i++ {
		dp[i] = i
	}

	for i := 2; i <= n; i++ {
		for j := i - 1; j >= 1; j-- {
			dp[i] = max(dp[i], (i-j)*dp[j])
		}
	}

	return dp[n]
}

//骚方法：4以上的数尽可能拆成3的和，如果剩4就拆成2和2
func IntegerBreak2(n int) int {
	if n <= 3 {
		return n - 1
	}

	product := 1
	for n > 4 {
		product *= 3
		n -= 3
	}
	product *= n

	return product
}

